class Linkedlist:

    root = None
    size = 0

    class Node:
        data,next = None,None

    # add node to the end of linked list
    # if the root node is None then add value to it
    # or else loop through the end of the linked list
    # and value to the end of the linked list
    def append(self,value):
        self.size += 1
        if self.root is None:
            self.root = self.Node()
            self.root.data = value
            self.root.next = None
            return

        temp = self.root
        while temp.next is not None:
            temp = temp.next

        add = self.Node()
        add.data = value
        # since this is the last node it points to None
        add.next = None
        # make last one to point to this new node
        temp.next = add
        return

    # create a new node and link to first node
    def add_first(self,value):
        # if the root node is empty then append it
        if self.root is None:
            self.append(value)
            return

        self.size += 1
        new = self.Node()
        new.data = value
        # point next to head node
        new.next = self.root
        # make this node as head node
        self.root = new
        return

    # add node after certain position in a linked list
    def add_middle(self,position,value):
        if position > self.size or position < 0:
            print "less than the actual size"
            return
        self.size += 1
        temp = self.root
        for i in range(0,position):
            temp = temp.next

        node = self.Node()
        node.data = value
        node.next = temp.next
        temp.next = node

    # delete a node from linked list
    # previous node of the node to be delete should point to next node of
    # node to be deleted
    def delete(self,value):
        current = self.root
        nextNode = None
        prevNode = None

        if self.root is None:
            print "empty linked list"
            return

        # if the root node has to be deleted
        self.size -= 1
        if self.root.data == value:
            temp = self.root
            self.root = self.root.next
            print "deleted root node"
            return

        while current.next is not None:
            nextNode = current.next
            prevNode = current

            if nextNode.data == value:
                prevNode.next = nextNode.next
                break

            current = current.next

    # Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
    # A : Just move the next node to current node's position
    def delete_with_only_single_pointer(self,value):
        temp = self.root
        flag = False
        while temp.next is not None:
            if temp.data == value:
                flag = True

            if flag:
                temp.data = temp.next.data

            temp = temp.next

        # delete the last value


    # retrieve all the nodes from linked list
    def show(self):
        temp = self.root
        while temp is not None:
            print temp.data
            temp = temp.next

        return

    # print linked list in reverse way without actually reversing it
    def printReverse(self):

        def rev(node):
            if node is None:
                return
            rev(node.next)
            print node.data

        rev(self.root)


    # get node from the beginning of the linked list
    def getANode(self,position):
        if self.size < position or position < 0:
            print "overflow"
            return

        temp = self.root
        for i in range(0,position):
            temp = temp.next

        return temp

    # get node from the end of the linked list
    def getNodeFromLast(self,position):
        last_position = self.size - position
        temp = self.root
        for i in range(0,last_position):
            temp = temp.next

        return temp.data

    # get middle of the linked list
    def getMiddle(self):
        fast = self.root
        slow = self.root
        count = 1
        while fast:
            if count%2 == 0:
                slow = slow.next

            fast = fast.next
            count+=1

        return slow.data

    # find how many times a element is repeated in a given linked list
    def find_repeted_element(self,element):
        temp = self.root
        count = 0
        while temp:
            if temp.data == element:
                count+=1
            temp = temp.next

        return count

    # detect a loop in a linked list
    # or else find if it is circular
    def isCircular(self):
        fast = self.root
        slow = self.root
        count = 1
        while fast:
            if count%2 == 0:
                slow = slow.next
            count+=1
            fast = fast.next
            if fast == slow:
                return True

        return False

    def isPalindrome(self):
        fast = self.root
        slow = self.root
        stack = []
        count = 0
        while fast:
            if count%2 == 0:
                stack.append(slow.data)
                slow = slow.next

            count += 1
            fast = fast.next


        if self.size%2 != 0:
            stack.pop()

        while slow is not None:
            element = stack.pop()
            if slow.data != element:
                print "not"
                return

            slow = slow.next

        print "is"

    # move the last element of the linked list to first
    def last_to_first(self):
        temp = self.root
        while temp.next.next is not None:
            temp = temp.next

        next = temp.next
        temp.next = None
        next.next = self.root
        self.root = next

    # reverse without recursion
    # reverse can be done by interchanging the links of the linked list
    # point current next link to previous link to make them reverse
    def reverse(self):
        next = None
        prev = None
        current = self.root
        while current is not None:
            next = current.next
            current.next = prev
            prev = current
            current = next

        self.root = prev

    
    def swap_pairs(self):
        current = self.root

        while current and current.next is not None:
            temp = current.data
            current.data = current.next.data
            current.next.data = temp
            current = current.next.next


    def reverse_only_k(self,k):
        current = self.root
        next = None
        prev = None

        # reverse first k nodes
        for i in range(0,k):
            next = current.next
            current.next = prev
            prev = current
            current = next

        # point root node to the tip of the reversed parital linked list
        self.root = prev
        temp = self.root
        # then loop through the end of the linked list
        while temp.next:
            temp = temp.next

        # current points to the other half of the linked list
        # make temp to connect to the rest of the nodes
        while current:
            temp.next = current
            temp = temp.next
            current = current.next

    def rotate_k_nodes(self,k):
        if k > self.size or k < 0:
            print "overflow"
            return

        temp = self.root
        for i in range(0,k):
            temp = temp.next

        pony_tail = temp

        while temp.next:
            temp = temp.next

        # attaching last node the starting of the linked list
        temp.next = self.root
        # making the kth node to be the root
        self.root = pony_tail.next
        # point the next to end or None
        pony_tail.next = None
        # make the kth node to point none


def main():
    ll = Linkedlist()
    ll.append(1)
    ll.append(2)
    ll.append(3)
    ll.append(4)
    ll.append(5)
    ll.append(6)
    ll.append(7)
    ll.append(8)

    ll.rotate_k_nodes(3)
    ll.show()


main()

